package leetcode_1_200;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_95_2 {
    public static void main(String[] args) {
        List<TreeNode> res = generateTrees(3);
    }
    private static List<TreeNode> generateTrees(int n) {
        if (n == 0)
            return new ArrayList<>();
        if (n == 1){
            List<TreeNode> res = new ArrayList<>();
            res.add(new TreeNode(1));
            return res;
        }
        return getRes(1, n);
    }
    private static List<TreeNode> getRes(int start, int end){
        List<TreeNode> res = new ArrayList<>();
        if (start > end){
            res.add(null);
            return res;
        }
        if (start == end){
            res.add(new TreeNode(start));
            return res;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> lRes = getRes(start, i - 1);
            List<TreeNode> rRes = getRes(i + 1, end);
            for (TreeNode lR : lRes) {
                for (TreeNode rR : rRes) {
                    TreeNode r = new TreeNode(i);
                    r.left = lR;
                    r.right = rR;
                    res.add(r);
                }
            }
        }
        return res;
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
